#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/5 16:18
# @USER    : Shengji He
# @File    : RemoveNthNodeEndList.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        """
        Given a linked list, remove the n-th node from the end of list and return its head.

        Example:

            Given linked list: 1->2->3->4->5, and n = 2.

            After removing the second node from the end, the linked list becomes 1->2->3->5.
        Note:
            Given n will always be valid.

        Follow up:

        Could you do this in one pass?

        :param head: ListNode
        :param n: int
        :return: ListNode
        """
        length = 0
        node = head

        while node:
            length += 1
            node = node.next
        node = head
        if length - n == 0:
            head = head.next
        else:
            while length - n - 1:
                node = node.next
                length -= 1
            node.next = node.next.next
        return head


if __name__ == '__main__':
    nums = [1, 2, 3, 4, 5]
    n = 4
    head = ListNode(nums.pop(0))
    temp = head
    for ele in nums:
        temp.next = ListNode(ele)
        temp = temp.next
    S = Solution()
    output = S.removeNthFromEnd(head, n)
    print('done')
